今天來跟大家聊聊動態規劃當中的一大經典：最長嚴格遞增子序列 Longest Increasing Subsequence：給你 n 個不相同的數字排成一列，對於任何一個子序列（不需要連續但是要按照左到右的順序），如果他是遞增的，我們就說這個子序列是一個遞增子序列 (Increasing Subsequence)。請你找出最長的遞增子序列的長度。

比方說輸入是 3, 6, 5, 1, 4, 9, 7, 8，那麼其中一個 LIS 是 3, 6, 7, 8、另一個可能的 LIS 是 1, 4, 7, 8，它們的長度都是 4。

LIS 有一個經典的 演算法如下：我們依序輸入這個序列的每個數字，使用一個中繼陣列 L[1..m] 儲存資訊，其中 L[i] 代表到目前為止長度為 i 的遞增子序列中，最小可能的結束值。一個重要的觀察是，這個序列永遠是遞減的： 能力越強，責任越大。 不是，是長度越長，結束值越小。所以對於每一個新的 數字進來，只要用二分搜尋法找出他的位置就行了。

以上面這個輸入來說，我們把計算過程都記錄下來：

加入3: 3
加入6: 3, 6
加入5: 3, 5
加入1: 1, 5
加入4: 1, 4
加入9: 1, 4, 9
加入7: 1, 4, 7
加入8: 1, 4, 7, 8

但這個演算法有很強的計算相依性啊！如果我們有 個執行緒，那麼頂多只能加快二分搜變成 分搜啊。這樣的時間複雜度就變成 ，是有一點點加速啦，但其實感覺不太出來，而且 code 又爆難寫。

找出不平行中的平行處

我們再來跑一次上面那個輸入，但是這時候我們把被踢掉的數字留下來，把新的數字墊高在上面。而最終盤面如下：

  4
1 5 7
3 6 9 8

堆得跟山一樣高。現在讓我們來進行另一個方向的觀察：每一個直排。對於每一個直排而言，從下往上的方向，必定是按照輸入序列由舊到新進行的。而且，注意到最左邊的直排：他就是前綴極小值們呀～然後呢，你可以證明說把前綴極小值丟掉以後，剩下的序列拿去做 LIS 也會跑出一模一樣的山。

所以我們得到一個有趣的作法：不斷地找前綴極小值，然後每一次找到以後就把所有這些極小值丟掉。看看要丟幾次才可以把所有數字通通都丟完，丟完的當下我們就知道 LIS 有多長了！

這樣時間複雜度會與最終 LIS 的長度有關。如果長度為 ，我們可以得到一個 複雜度的演算法，相當有趣吧！不過厲害的你想必注意到了：上面這個時間複雜度只有在 的時候會比原本的 演算法有幫助XD

我們明天再繼續討論看看有沒有更好的作法～

參考資料

1. “PARALLEL ALGORITHMS FOR PATIENCE SORTING AND LONGEST INCREASING SUBSEQUENCE” Nakashima, Fujiwara, 2006.
2. LIS in Parallel (BSP Model) https://mass-communicating.com/files/plis_talk.pdf